Wireless communication systems are widely deployed to provide various types of communications such as voice and data. One such system is wide band code division multiple access (WCDMA), which has been adopted in various competing wireless communication standards, for example the third generation partnership project 3GPP.
To overcome data corruption that can occur during RF transmission, the different wireless communication standards typically use some form of channel coding, where one common channel coding technique is turbo coding.
Turbo coding involves the use of a turbo encoder for encoding a code segment (i.e. a data packet) and a turbo decoder for the decoding of the encoded code segment. A turbo encoder typically includes a pair of convolutional encoders, one of which receives information bits (i.e. systematic bits) while the other convolutional encoder receives vinterleaved information bits. The information bits are shuffled (interleaved) in accordance with a specified interleaving scheme. The pair of convolutional encoders output two sequences of parity bits that are modulated and transmitted to a receiver. The systematic bits are also modulated and transmitted to the receiver.
The third generation partnership project (3GPP) defines an interleaver that performs inter row interleaving that is followed by intra row interleaving. There interleaving is applied on a rectangular matrix that include data elements that are arranged in rows and columns. The 3GPP standard defines the number of row and columns of the rectangular matrix—in response to the size of the data block. For example, for a data block of 40 till 159 data elements there are five rows, for a data block of 160 till 200 data elements or of 481 till 530 data elements there are ten rows and for any other size of data block there are twenty rows. The 3GPP standard also defines the number of columns of the rectangular matrix, a prime number P, and a primitive root v, all being used during the intra row permutation and all dependent upon the size of the data block.
The intra row permutation includes multiple permutations that are knows as a primary permutation and a secondary permutation. The primary permutations precedes the secondary permutation. The primary permutation is applied on the elements in a row while the secondary permutation is applied on the results of the primary permutation. The results of the primary permutation are used to select an entry of a data structure (also known as an S-table that stores the results of applying the secondary permutation. In data blocks that are very long, the S-table is very long and each interleaving process requires many accesses to the S-table. The 3GPP standard also defines which primary permutation functions to associate with which rows of the rectangular matrix.
For simplicity of explanation, in the following a modulo operation is denoted as “%”—the term A%B means applying a B modulo operation on variable A.
For a data block that includes 40 data elements the following primary permutation functions are defined: P1(A)=A%6, P2(A)=(5A)%6, and the secondary permutation is S(A)=3A%7 wherein 3A stands for 3 by the power of A. P1(A) defines a permutation P1 that includes the following elements (in the following order): 0, 1, 2, 3, 4, 5. P2(A) defines a permutation P2 that includes the following elements (in the following order): 0, 5, 4, 3, 2, 1. S(A) defines a permutation S that includes the following elements: 1, 3, 2, 6, 4, 5.
The calculation of P2(A) and S(A) is complex, and the complexity of the permutation functions dramatically increases with an increase in the size of the data block. Due to the complexity of these calculations, S(A) is calculated in advance—and the possible values of S(A) are stored in the mentioned above S table. The calculation of P2(A) may require a complex and area consuming modulo circuit, especially when it is applied on large numbers.